package leetcode;

import structs.ListNode;

public class test0021 {

    public static void main(String[] args) {
        // [[1,4,5],[1,3,4],[2,6]]
        ListNode[] listNodes = new ListNode[3];
        ListNode a = new ListNode(1);
        a.next = new ListNode(4);
        a.next.next = new ListNode(5);

        ListNode b = new ListNode(1);
        b.next = new ListNode(3);
        b.next.next = new ListNode(4);

        ListNode c = new ListNode(2);
        c.next = new ListNode(6);

        listNodes[0] = a;
        listNodes[1] = b;
        listNodes[2] = c;

        ListNode listNode = mergeKLists(listNodes);
        while(listNode != null){
            System.out.print(listNode.val + "->");
            listNode = listNode.next;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode res = new ListNode(0);
        ListNode tempRes = res;
        boolean hasNode = false;
        int min = Integer.MAX_VALUE;
        int val;
        int index = -1;

        while(true){
            min = Integer.MAX_VALUE;
            hasNode = false;

            for(int i = 0; i < lists.length; i++){
                hasNode = hasNode || (lists[i] != null);
                if(lists[i] == null) continue;

                val = lists[i].val;
                if(min > val){
                    min = val;
                    index = i;
                }
            }

            if(!hasNode) break;

            if(lists[index] != null){
                lists[index] = lists[index].next;
            }

            tempRes.next = new ListNode(min);
            tempRes = tempRes.next;
        }

        return res.next;

    }
}
